package LearnAlgorithm.e_多维数组and矩阵;

import java.util.Arrays;

/*
{-1,-1,-1}
{-1,2,2}
{-1,-1,-1}

上面二维数组的子矩阵是这样的：
{-1}
或者
{-1,-1}
{-1,2}
或者
{2,2}
或者
{-1,2,2}
{-1,-1,-1}
或者
{-1}
{-1}
{-1}

必须是长方形(包括正方形)！！！！！！！！
给定一个矩阵matrix,其中的值有正、有负、有0 ,返回子矩阵的最大累加和
例如:
{-1,-1,-1}
{-1,2,2}
{-1,-1,-1}
其中最大累加和的子矩阵为:
{2,2}
所以返回4

 */
public class f二维数组返回子矩阵最大累加和 {
	public static void main(String[] args) {
		int[][] matrix = new int[][] {
			{-1,-1,-1},
			{-1,2,2},
			{-1,-1,-1}
		};
		long before = System.currentTimeMillis();
		int find = find(matrix);
		util.Util.duration(before);
		System.out.println(find);
	}
	
	/**
	 * O(N^3)
	 * 已经很优化了
	 * @param matrix
	 * @return
	 */
	public static int find(int[][] matrix) {
		if (matrix.length == 0) {
			return 0;
		}
		int beginRow = 0;//定义起始行
		int row = matrix.length;//定义行数
		int col = matrix[0].length;//定义列数
		int[] makeSumArr = new int[col];//定义	用来累加的	帮助数组
		int maxSum = 0;//定义“目标子矩阵的最大累加的数值”
		while (beginRow < row) {//开始遍历
			for(int currentRow = beginRow; currentRow < row; currentRow++) {//(currentRow-beginRow)作为当前操作的矩阵的行数
				for (int currentCol = 0; currentCol < col; currentCol++) {//(col)作为当前操作的矩阵的最大列数
					makeSumArr[currentCol] += matrix[currentRow][currentCol];//将当前操作的矩阵压缩成一维数组
				}
				int currentRowSum = oneFind(makeSumArr);//运用一维数组求子数组最大累加的方法，求当前操作的矩阵的最大累加；此行代码必须放到这里
				if (currentRowSum > maxSum) {
					maxSum = currentRowSum;//更新“目标子矩阵的最大累加的数值”；此if判断代码必须放到这里
				}
			}
			/*
			上面的嵌套for循环很有讲究
			举例来说：
			beginRow = 0
				{-1,-1,-1}
				和
				{-1,-1,-1}
				{-1,2,2}
				和
				{-1,-1,-1}
				{-1,2,2}
				{-1,-1,-1}
			
			beginRow = 1
				{-1,2,2},
				和
				{-1,2,2},
				{-1,-1,-1}
				
			beginRow = 2
				{-1,-1,-1}
				
			懂了没有？所有情况都考虑到了
			 */
			Arrays.fill(makeSumArr, 0);//清空帮助数组
			beginRow++;//更新起始行
		}
		return maxSum;
	}
	
	/**
	 * O(N)
	 * @param arr
	 * @return
	 */
	public static int oneFind(int[] arr) {
		if (arr.length == 0) {
			return 0;
		}
		int sumI = arr[0];
		int maxSum = sumI;
		for (int i = 1; i < arr.length; i++) {
			if (sumI >= 0) {
				sumI += arr[i];
			} else {
				sumI = arr[i];
			}
			if (sumI > maxSum) {
				maxSum = sumI;
			}
		}
		return maxSum;
	}
}
